from typing import List

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        m, n = len(matrix), len(matrix[0])
        if numSelect < n:
            col_sum = [sum([ r[i] for r in matrix]) for i in range(n)]
            row_sum = [sum(r) for r in matrix]

            range_ = range(1, 1<<n)
            res = 0
            for j in range_:
                if j.bit_count() == numSelect:
                    # 每一列是否选择
                    l = list(map(int,list(bin(j))[2:]))
                    l = [0]*(n-len(l)) + l

                    # col_sum_sorted = sorted(enumerate(col_sum), key=lambda x: x[1], reverse=True)
                    # 选中列对应的行和
                    selected_sum = [sum([ r[c]*l[c] for c in range(n)]) for r in matrix]
                    res = max(res, sum([row_sum[i]==selected_sum[i] for i in range(m)]))
            return res

        return m

if __name__ == '__main__':
    matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]]
    numSelect = 2
    s = Solution()
    res = s.maximumRows(matrix, numSelect)
    print(res)